/*
 * 图论算法模板库 - 常用图算法的高效实现
 * 使用场景: 图相关的算法题，如最短路径、连通性、生成树等
 * 包含: DFS/BFS、最短路径、最小生成树、强连通分量、拓扑排序等
 */

#pragma once
#include "basic_template.hpp"

// 图的基本表示 - 支持有向图和无向图，带权图和无权图
// 使用场景: 作为其他图算法的基础数据结构
// 特点: 同时支持邻接表和带权邻接表两种表示方式
class Graph
{
public:
    int n;
    vector<vector<int>> adj;
    vector<vector<pair<int, int>>> weighted_adj;

    Graph(int vertices) : n(vertices)
    {
        adj.resize(n);
        weighted_adj.resize(n);
    }

    void add_edge(int u, int v, bool directed = false)
    {
        adj[u].push_back(v);
        if (!directed)
            adj[v].push_back(u);
    }

    void add_weighted_edge(int u, int v, int w, bool directed = false)
    {
        weighted_adj[u].push_back({v, w});
        if (!directed)
            weighted_adj[v].push_back({u, w});
    }
};

// DFS遍历 - 深度优先搜索，用于图的遍历和性质分析
// 使用场景: 连通性检测、环检测、拓扑排序、强连通分量
// 时间复杂度: O(V + E)
// 典型应用: 迷宫求解、岛屿问题、括号匹配、表达式求值
// 特点: 记录发现时间和完成时间，可用于高级图算法
class DFS
{
private:
    vector<bool> visited;
    vector<int> discovery, finish, parent;
    int timer;

public:
    DFS(const Graph &g) : visited(g.n, false), discovery(g.n),
                          finish(g.n), parent(g.n, -1), timer(0) {}

    void dfs(const Graph &g, int u)
    {
        visited[u] = true;
        discovery[u] = timer++;

        for (int v : g.adj[u]) {
            if (!visited[v]) {
                parent[v] = u;
                dfs(g, v);
            }
        }

        finish[u] = timer++;
    }

    void dfs_all(const Graph &g)
    {
        for (int i = 0; i < g.n; ++i) {
            if (!visited[i]) {
                dfs(g, i);
            }
        }
    }

    bool is_visited(int u) const { return visited[u]; }
    int get_discovery(int u) const { return discovery[u]; }
    int get_finish(int u) const { return finish[u]; }
    int get_parent(int u) const { return parent[u]; }
};

// BFS遍历 - 广度优先搜索，用于最短路径和层次遍历
// 使用场景: 无权图最短路径、层次遍历、最小步数问题
// 时间复杂度: O(V + E)
// 典型应用: 迷宫最短路径、社交网络距离、游戏状态搜索
// 特点: 保证找到最短路径（边权为1时）
class BFS
{
private:
    vector<int> distance, parent;
    vector<bool> visited;

public:
    BFS(const Graph &g) : distance(g.n, -1), parent(g.n, -1), visited(g.n, false) {}

    void bfs(const Graph &g, int start)
    {
        queue<int> q;
        visited[start] = true;
        distance[start] = 0;
        q.push(start);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : g.adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    distance[v] = distance[u] + 1;
                    parent[v] = u;
                    q.push(v);
                }
            }
        }
    }

    int get_distance(int u) const { return distance[u]; }
    int get_parent(int u) const { return parent[u]; }
    bool is_reachable(int u) const { return visited[u]; }

    vector<int> get_path(int target) const
    {
        if (!visited[target])
            return {};

        vector<int> path;
        for (int v = target; v != -1; v = parent[v]) {
            path.push_back(v);
        }
        reverse(path.begin(), path.end());
        return path;
    }
};

// Dijkstra最短路径 - 单源最短路径算法（非负权边）
// 使用场景: 带权图的最短路径问题，边权非负
// 时间复杂度: O((V + E) log V) 使用优先队列
// 典型应用: 地图导航、网络路由、任务调度
// 注意: 不能处理负权边，需要负权边用Bellman-Ford算法
class Dijkstra
{
private:
    vector<ll> dist;
    vector<int> parent;

public:
    Dijkstra(const Graph &g) : dist(g.n, LINF), parent(g.n, -1) {}

    void dijkstra(const Graph &g, int start)
    {
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

        dist[start] = 0;
        pq.push({0, start});

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();

            if (d > dist[u])
                continue;

            for (auto [v, w] : g.weighted_adj[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    parent[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }
    }

    ll get_distance(int u) const { return dist[u]; }

    vector<int> get_path(int target) const
    {
        if (dist[target] == LINF)
            return {};

        vector<int> path;
        for (int v = target; v != -1; v = parent[v]) {
            path.push_back(v);
        }
        reverse(path.begin(), path.end());
        return path;
    }
};

// 拓扑排序
vector<int> topological_sort(const Graph &g)
{
    vector<int> in_degree(g.n, 0);
    for (int u = 0; u < g.n; ++u) {
        for (int v : g.adj[u]) {
            in_degree[v]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < g.n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> result;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);

        for (int v : g.adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    return result.size() == g.n ? result : vector<int>();
}

// 强连通分量 (Kosaraju算法)
class SCC
{
private:
    vector<bool> visited;
    vector<int> order, component;
    int comp_count;

    void dfs1(const Graph &g, int u, vector<int> &finish_order)
    {
        visited[u] = true;
        for (int v : g.adj[u]) {
            if (!visited[v]) {
                dfs1(g, v, finish_order);
            }
        }
        finish_order.push_back(u);
    }

    void dfs2(const Graph &g, int u, int comp_id)
    {
        component[u] = comp_id;
        for (int v : g.adj[u]) {
            if (component[v] == -1) {
                dfs2(g, v, comp_id);
            }
        }
    }

public:
    SCC(const Graph &g) : visited(g.n, false), component(g.n, -1), comp_count(0) {}

    void find_scc(const Graph &g)
    {
        vector<int> finish_order;

        // 第一次DFS
        for (int i = 0; i < g.n; ++i) {
            if (!visited[i]) {
                dfs1(g, i, finish_order);
            }
        }

        // 构建转置图
        Graph transpose(g.n);
        for (int u = 0; u < g.n; ++u) {
            for (int v : g.adj[u]) {
                transpose.add_edge(v, u, true);
            }
        }

        // 第二次DFS
        reverse(finish_order.begin(), finish_order.end());
        for (int u : finish_order) {
            if (component[u] == -1) {
                dfs2(transpose, u, comp_count++);
            }
        }
    }

    int get_component(int u) const { return component[u]; }
    int get_component_count() const { return comp_count; }
};

// 最小生成树 (Kruskal算法)
struct Edge {
    Edge(int u, int v, int w) : u(u), v(v), w(w) {}
    int u, v, w;
    bool operator<(const Edge &other) const
    {
        return w < other.w;
    }
};

ll kruskal_mst(int n, vector<Edge> &edges)
{
    sort(edges.begin(), edges.end());
    UnionFind uf(n);

    ll mst_weight = 0;
    int edges_added = 0;

    for (const Edge &e : edges) {
        if (uf.unite(e.u, e.v)) {
            mst_weight += e.w;
            edges_added++;
            if (edges_added == n - 1)
                break;
        }
    }

    return edges_added == n - 1 ? mst_weight : -1;
}

// 二分图检测 - 判断图是否为二分图
// 使用场景: 二分图匹配、图着色、调度问题
// 时间复杂度: O(V + E)
// 典型应用: 任务分配、冲突检测、图着色
bool is_bipartite(const Graph &g)
{
    vector<int> color(g.n, -1);

    for (int start = 0; start < g.n; ++start) {
        if (color[start] == -1) {
            queue<int> q;
            color[start] = 0;
            q.push(start);

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                for (int v : g.adj[u]) {
                    if (color[v] == -1) {
                        color[v] = 1 - color[u];
                        q.push(v);
                    } else if (color[v] == color[u]) {
                        return false;
                    }
                }
            }
        }
    }

    return true;
}

// Hierholzer算法 - 寻找欧拉路径/回路
// 使用场景: 一笔画问题、路径规划、网络遍历
// 时间复杂度: O(V + E)
// 典型应用: 邮递员问题、DNA序列重建、电路设计
// 注意: 需要先检查欧拉路径/回路存在性
class Hierholzer
{
private:
    vector<vector<int>> adj;
    vector<int> in_degree, out_degree;
    int n;

public:
    Hierholzer(int vertices) : n(vertices), adj(vertices), in_degree(vertices, 0), out_degree(vertices, 0) {}

    void add_edge(int u, int v, bool directed = true)
    {
        adj[u].push_back(v);
        out_degree[u]++;
        in_degree[v]++;

        if (!directed) {
            adj[v].push_back(u);
            out_degree[v]++;
            in_degree[u]++;
        }
    }

    // 检查是否存在欧拉路径/回路
    pair<bool, int> check_euler_path()
    {
        int start_nodes = 0, end_nodes = 0;
        int start = 0;

        for (int i = 0; i < n; i++) {
            if (out_degree[i] - in_degree[i] == 1) {
                start_nodes++;
                start = i;
            } else if (in_degree[i] - out_degree[i] == 1) {
                end_nodes++;
            } else if (in_degree[i] != out_degree[i]) {
                return {false, -1}; // 不存在欧拉路径
            }
        }

        if (start_nodes == 0 && end_nodes == 0) {
            return {true, 0}; // 欧拉回路，可以从任意点开始
        } else if (start_nodes == 1 && end_nodes == 1) {
            return {true, start}; // 欧拉路径，必须从start开始
        }

        return {false, -1};
    }

    // 寻找欧拉路径
    vector<int> find_euler_path()
    {
        auto [has_path, start] = check_euler_path();
        if (!has_path)
            return {};

        vector<vector<int>> temp_adj = adj;
        vector<int> path;
        stack<int> st;
        st.push(start);

        while (!st.empty()) {
            int u = st.top();
            if (!temp_adj[u].empty()) {
                int v = temp_adj[u].back();
                temp_adj[u].pop_back();
                st.push(v);
            } else {
                path.push_back(u);
                st.pop();
            }
        }

        reverse(path.begin(), path.end());
        return path;
    }
};

// Tarjan算法 - 强连通分量、桥、割点
// 使用场景: 网络连通性分析、关键路径识别、图的分解
// 时间复杂度: O(V + E)
// 典型应用: 网络可靠性、社交网络分析、编译器优化
class Tarjan
{
private:
    vector<vector<int>> adj;
    vector<int> disc, low, parent;
    vector<bool> visited;
    vector<pair<int, int>> bridges;
    vector<int> articulation_points;
    vector<vector<int>> sccs;
    vector<bool> on_stack;
    stack<int> st;
    int timer, n;

    void bridge_dfs(int u)
    {
        visited[u] = true;
        disc[u] = low[u] = ++timer;

        for (int v : adj[u]) {
            if (!visited[v]) {
                parent[v] = u;
                bridge_dfs(v);
                low[u] = min(low[u], low[v]);

                // 如果low[v] > disc[u]，则(u,v)是桥
                if (low[v] > disc[u]) {
                    bridges.push_back({min(u, v), max(u, v)});
                }
            } else if (v != parent[u]) {
                low[u] = min(low[u], disc[v]);
            }
        }
    }

    void articulation_dfs(int u)
    {
        visited[u] = true;
        disc[u] = low[u] = ++timer;
        int children = 0;
        bool is_articulation = false;

        for (int v : adj[u]) {
            if (!visited[v]) {
                children++;
                parent[v] = u;
                articulation_dfs(v);
                low[u] = min(low[u], low[v]);

                // 根节点是割点的条件
                if (parent[u] == -1 && children > 1) {
                    is_articulation = true;
                }

                // 非根节点是割点的条件
                if (parent[u] != -1 && low[v] >= disc[u]) {
                    is_articulation = true;
                }
            } else if (v != parent[u]) {
                low[u] = min(low[u], disc[v]);
            }
        }

        if (is_articulation) {
            articulation_points.push_back(u);
        }
    }

    void scc_dfs(int u, vector<int> &current_scc)
    {
        visited[u] = true;
        disc[u] = low[u] = ++timer;
        st.push(u);
        on_stack[u] = true;

        for (int v : adj[u]) {
            if (!visited[v]) {
                scc_dfs(v, current_scc);
                low[u] = min(low[u], low[v]);
            } else if (on_stack[v]) {
                low[u] = min(low[u], disc[v]);
            }
        }

        // 如果u是强连通分量的根
        if (low[u] == disc[u]) {
            vector<int> scc;
            int v;
            do {
                v = st.top();
                st.pop();
                on_stack[v] = false;
                scc.push_back(v);
            } while (v != u);
            sccs.push_back(scc);
        }
    }

public:
    Tarjan(int vertices) : n(vertices), adj(vertices), disc(vertices), low(vertices),
                           parent(vertices, -1), visited(vertices, false), on_stack(vertices, false), timer(0) {}

    void add_edge(int u, int v, bool directed = true)
    {
        adj[u].push_back(v);
        if (!directed) {
            adj[v].push_back(u);
        }
    }

    // 寻找所有桥
    vector<pair<int, int>> find_bridges()
    {
        bridges.clear();
        fill(visited.begin(), visited.end(), false);
        fill(parent.begin(), parent.end(), -1);
        timer = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                bridge_dfs(i);
            }
        }

        return bridges;
    }

    // 寻找所有割点
    vector<int> find_articulation_points()
    {
        articulation_points.clear();
        fill(visited.begin(), visited.end(), false);
        fill(parent.begin(), parent.end(), -1);
        timer = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                articulation_dfs(i);
            }
        }

        return articulation_points;
    }

    // 寻找强连通分量
    vector<vector<int>> find_sccs()
    {
        sccs.clear();
        fill(visited.begin(), visited.end(), false);
        fill(on_stack.begin(), on_stack.end(), false);
        timer = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                vector<int> current_scc;
                scc_dfs(i, current_scc);
            }
        }

        return sccs;
    }
};
